home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / cagd_lib / afd_cube.c next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  8.4 KB  |  248 lines
  1. /******************************************************************************
  2. * AFD_Cube.c - Cubic Adaptive forward Differencing code.              *
  3. *                                          *
  4. * This file's code is based on the following cubic polynomial basis function  *
  5. *                                          *
  6. *              C2  2    C3  3                          *
  7. * C(t) = C0 + C1 t + --- t  + --- t    ,   Ci are the coefficients.          *
  8. *              2           3                          *
  9. *                                          *
  10. * For more, see:                                  *
  11. *                                          *
  12. * 1. S. Chang, M. Shantz and R.Rocchetti. Rendering Cubic Curves and          *
  13. *    Surfaces with Integer Adaptive Forward Differencing. Computer Graphics,  *
  14. *    Vol. 23, Num. 3, pp. 157-166, Siggraph Jul. 1989.                  *
  15. * 2. M. Shantz and S. L. Lien. Shading Bicubic Patches. Computer Graphics,    *
  16. *    Vol. 21, Num. 4, pp. 189-196, Siggraph Jul. 1987.                  *
  17. * 3. M. Shantz and S. Chang. Rendering Trimmed NURBS with Adaptive Forward    *
  18. *    Differencing. Computer Graphics, Vol. 22, Num. 4, pp. 189-198,          *
  19. *    Siggraph Aug. 1988.                              *
  20. *******************************************************************************
  21. * Written by Gershon Elber, Jan. 93.                          *
  22. ******************************************************************************/
  23.  
  24. #include <ctype.h>
  25. #include <stdio.h>
  26. #include <string.h>
  27. #include "cagd_loc.h"
  28.  
  29. /******************************************************************************
  30. * Given four coefficents of a cubic Bezier curve, computes the four          *
  31. * coefficients of the cubic afd basis functions, in place.              *
  32. ******************************************************************************/
  33. void AfdCnvrtCubicBzrToAfd(CagdRType Coef[4])
  34. {
  35.     CagdRType AfdCoef[4];
  36.  
  37.     AfdCoef[0] = Coef[0];
  38.     AfdCoef[1] = Coef[3] - Coef[0];
  39.     AfdCoef[2] = 6.0 * Coef[3] - 12.0 * Coef[2] + 6.0 * Coef[1];
  40.     AfdCoef[3] = 6.0 * Coef[3] - 18.0 * Coef[2] + 18.0 * Coef[1] - 6.0 * Coef[0];
  41.     CAGD_GEN_COPY(Coef, AfdCoef, sizeof(CagdRType) * 4);
  42. }
  43.  
  44. /******************************************************************************
  45. * Given four coefficents of a cubic afd polynomial, apply the L ( half the    *
  46. * step size ) n times to them, in place.                      *
  47. * We basically precomputed L^n and apply it here once. Every instance of L    *
  48. * half the domain and so L^n divides the domain by 2^n.                  *
  49. ******************************************************************************/
  50. void AfdApplyLn(CagdRType Coef[4], int n)
  51. {
  52.     CagdRType AfdCoef[4];
  53.  
  54.     switch (n) {
  55.     case 1:
  56.         AfdCoef[0] = Coef[0];
  57.         AfdCoef[1] = Coef[1] / 2.0 - Coef[2] / 8.0 + Coef[3] / 16.0;
  58.         AfdCoef[2] = Coef[2] / 4.0 - Coef[3] / 8.0;
  59.         AfdCoef[3] = Coef[3];
  60.         break;
  61.     case 2:
  62.         AfdCoef[0] = Coef[0];
  63.         AfdCoef[1] = Coef[1] / 4.0 - Coef[2] * 3.0 / 32.0 +
  64.                         Coef[3] * 7.0 / 128.0;
  65.         AfdCoef[2] = Coef[2] / 16.0 - Coef[3] * 3.0 / 64.0;
  66.         AfdCoef[3] = Coef[3] / 64.0;
  67.         break;
  68.     case 3:
  69.         AfdCoef[0] = Coef[0];
  70.         AfdCoef[1] = Coef[1] / 8.0 - Coef[2] * 7.0 / 128.0 +
  71.                         Coef[3] * 35.0 / 1024.0;
  72.         AfdCoef[2] = Coef[2] / 64 - Coef[3] * 7.0 / 512.0;
  73.         AfdCoef[3] = Coef[3] / 512.0;
  74.         break;
  75.     case 4:
  76.         AfdCoef[0] = Coef[0];
  77.         AfdCoef[1] = Coef[1] / 16.0 - Coef[2] * 15.0 / 512.0 +
  78.                         Coef[3] * 155.0 / 8192.0;
  79.         AfdCoef[2] = Coef[2] / 256 - Coef[3] * 15.0 / 4096.0;
  80.         AfdCoef[3] = Coef[3] / 4096.0;
  81.         break;
  82.     case 5:
  83.         AfdCoef[0] = Coef[0];
  84.         AfdCoef[1] = Coef[1] / 32.0 - Coef[2] * 31.0 / 2048.0 +
  85.                         Coef[3] * 651.0 / 65536.0;
  86.         AfdCoef[2] = Coef[2] / 1024 - Coef[3] * 31.0 / 32768.0;
  87.         AfdCoef[3] = Coef[3] / 262144.0;
  88.         break;
  89.     case 6:
  90.         AfdCoef[0] = Coef[0];
  91.         AfdCoef[1] = Coef[1] / 64.0 - Coef[2] * 63.0 / 8192.0 +
  92.                         Coef[3] * 2667.0 / 524288.0;
  93.         AfdCoef[2] = Coef[2] / 4096.0 - Coef[3] * 63.0 / 262144.0;
  94.         AfdCoef[3] = Coef[3] / 262144.0;
  95.         break;
  96.     case 7:
  97.         AfdCoef[0] = Coef[0];
  98.         AfdCoef[1] = Coef[1] / 128.0 - Coef[2] * 127.0 / 32768.0 +
  99.                         Coef[3] * 10795.0 / 4194304.0;
  100.         AfdCoef[2] = Coef[2] / 16384.0 - Coef[3] * 127.0 / 2097152.0;
  101.         AfdCoef[3] = Coef[3] / 2097152.0;
  102.         break;
  103.     case 8:
  104.         AfdCoef[0] = Coef[0];
  105.         AfdCoef[1] = Coef[1] / 256.0 - Coef[2] * 255.0 / 131072.0 +
  106.                         Coef[3] * 43435.0 / 33554432.0;
  107.         AfdCoef[2] = Coef[2] / 65536.0 - Coef[3] * 255.0 / 16777216.0;
  108.         AfdCoef[3] = Coef[3] / 16777216.0;
  109.         break;
  110.     case 9:
  111.         AfdCoef[0] = Coef[0];
  112.         AfdCoef[1] = Coef[1] / 512.0 - Coef[2] * 511.0 / 524288.0 +
  113.                     Coef[3] * 174251.0 / 268435456.0;
  114.         AfdCoef[2] = Coef[2] / 262144.0 - Coef[3] * 511.0 / 134217728.0;
  115.         AfdCoef[3] = Coef[3] / 134217728.0;
  116.         break;
  117.     case 10:
  118.         AfdCoef[0] = Coef[0];
  119.         AfdCoef[1] = Coef[1] / 1024.0 - Coef[2] * 1023.0 / 2097152.0 +
  120.                     Coef[3] * 698027.0 / 2147483648.0;
  121.         AfdCoef[2] = Coef[2] / 1048576.0 - Coef[3] * 1023.0 / 1073741824.0;
  122.         AfdCoef[3] = Coef[3] / 1073741824.0;
  123.         break;
  124.     default:
  125.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  126.         return;
  127.     }
  128.     CAGD_GEN_COPY(Coef, AfdCoef, sizeof(CagdRType) * 4);
  129. }
  130.  
  131. /******************************************************************************
  132. * Given four coefficents of a cubic afd polynomial, apply the E ( step by 1 ) *
  133. * in place.                                      *
  134. ******************************************************************************/
  135. void AfdApplyEStep(CagdRType Coef[4])
  136. {
  137.     Coef[0] += Coef[1];
  138.     Coef[1] += Coef[2];
  139.     Coef[2] += Coef[3];
  140. }
  141.  
  142. /******************************************************************************
  143. * Given four coefficents of a cubic Bezier curve, computes the four          *
  144. * coefficients of the cubic afd basis functions and step along them to create *
  145. * a piecewise polynomial approximating the curve.                  *
  146. *   if NonAdaptive is TRUE then 2^Log2Step constant steps are taken, creating *
  147. * 2^Log2Step + 1 points along the curve.                      *
  148. *   Otherwise the full blown adaptive algorithm is used.              *
  149. ******************************************************************************/
  150. void AfdComputePolyline(CagdRType Coef[4], CagdRType *Poly, int Log2Step,
  151.                             CagdBType NonAdaptive)
  152. {
  153.     int i;
  154.     int n = 1 << Log2Step;
  155.  
  156.     AfdCnvrtCubicBzrToAfd(Coef);
  157.     AfdApplyLn(Coef, Log2Step);
  158.  
  159.     if (NonAdaptive) {
  160.     for (i = 0; i <= n; i++) {
  161.         Poly[i] = Coef[0];
  162.         AfdApplyEStep(Coef);
  163.     }
  164.     }
  165.     else
  166.     {
  167.     FATAL_ERROR(CAGD_ERR_AFD_NO_SUPPORT);
  168.     }
  169. }
  170.  
  171. /******************************************************************************
  172. * Samples the curves at FineNess location equally spaced in the Bezier        *
  173. * parametric domain [0..1]. If Cache is enabled, and FineNess is power of     *
  174. * two, upto or equal to CacheFineNess, the cache is used, otherwise the       *
  175. * points are evaluated manually for each of the samples.              *
  176. * Data is saved at the Points array of vectors (according to Curve PType),    *
  177. * each vector is assumed to be allocated for FineNess CagdRType points.          *
  178. * Bezier curve must be cubic.                              *
  179. ******************************************************************************/
  180. void AfdBzrCrvEvalToPolyline(CagdCrvStruct *Crv, int FineNess,
  181.                             CagdRType *Points[])
  182. {
  183.     CagdBType
  184.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  185.     int i, j,
  186.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  187.     CagdRType
  188.     **CtlPoints = Crv -> Points;
  189.  
  190.     if (Crv -> Order != 4)
  191.     FATAL_ERROR(CAGD_ERR_CUBIC_EXPECTED);
  192.  
  193.     for (i = IsNotRational; i <= MaxCoord; i++) {
  194.     CagdRType Coef[4];
  195.  
  196.     for (j = 0; j < 4; j++)
  197.         Coef[j] = CtlPoints[i][j];
  198.  
  199.     AfdComputePolyline(Coef, Points[j], FineNess, TRUE);
  200.     }
  201. }
  202.  
  203. #ifdef DEBUG_AFD
  204.  
  205. /* If this section is defined, this file can be compiled stand alone. */
  206.  
  207. void CagdFatalError(CagdFatalErrorType ErrID)
  208. {
  209. }
  210.  
  211. void main(int argc, char **argv)
  212. {
  213.     CagdRType
  214.     Poly[1025],
  215.     Coef[4] = { 0.0, 1.0, 2.0, 3.0 };
  216.     int i,
  217.     Log2Step = 6;
  218.  
  219.     while (argc >= 2) {
  220.     if (argc >= 2 && strcmp( argv[1], "-s" ) == 0) {
  221.         Log2Step = atoi( argv[2] );
  222.         argc -= 2;
  223.         argv += 2;
  224.     }
  225.     else if (argc >= 2 && strcmp( argv[1], "-c" ) == 0) {
  226.         sscanf(argv[2], "%lf", &Coef[0]);
  227.         sscanf(argv[3], "%lf", &Coef[1]);
  228.         sscanf(argv[4], "%lf", &Coef[2]);
  229.         sscanf(argv[5], "%lf", &Coef[3]);
  230.         argc -= 5;
  231.         argv += 5;
  232.     }
  233.     else {
  234.         fprintf(stderr, "Wrong command line");
  235.         exit(1);
  236.     }
  237.     }
  238.  
  239.     printf("Steps = %d, Coef = %lf %lf %lf %lf\n",
  240.        Log2Step, Coef[0], Coef[1], Coef[2], Coef[3]);
  241.  
  242.     AfdComputePolyline(Coef, Poly, Log2Step, TRUE);
  243.     for (i = 0; i <= (1 << Log2Step); i++)
  244.     printf("%d = %lg\n", i, (double) Poly[i]);
  245. }
  246.  
  247. #endif /* DEBUG_AFD */
  248.